package wh.单链表合并算法;

public class Merge {
    /**
     * 单链表合并算法
     */
    public static void main(String[] args) {
        ListNode l1 = new ListNode(1,new ListNode(3,new ListNode(5)));
        ListNode l2 = new ListNode(2,new ListNode(4,new ListNode(6,new ListNode(8,new ListNode(10)))));
        ListNode listNode = mergeTwoLists(l1, l2);
        System.out.println(listNode.val);
    }
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //指针p指向的是新建的头节点dummyHead
        //基本类型int的默认值为0
        ListNode dummyHead = new ListNode(0);
        ListNode p = dummyHead;
        //p1,p2分别指向单链表l1和l2的头节点
        ListNode p1=l1,p2=l2;
        while(p1!=null && p2!=null){
            int x = p1.val;
            int y = p2.val;
            if(x<=y){
                p.next=p1;
                p1 = p1.next;
                p = p.next;
            }
            else {
                p.next=p2;
                p2= p2.next;
                p = p.next;
            }
        }
        while(p1!=null){
            p.next = p1;
            break;
        }
        while(p2!=null){
            p.next = p2;
            break;
        }
        //这里返回的是首节点
        return dummyHead.next;
    }

}
